Лемма о разрыве цикла

Ребро $e$ принадлежит некоторому циклу графа $G \implies$ число компонент связности графов $G$ и $G - e$ совпадает.

Если ребро $e$ входит в некоторый цикл, то оно входит и в простой цикл $e, e'_1, \dots, e'_l$. Пусть вершины $u$ и $v$ связаны в $G$; докажем, что они связаны и в $G-e$. В $G$ найдется $(u, v)$-путь, скажем, $e_1, e_2, \dots, e_k$. Если в этом пути нет ребра $e$, то $u$ и $v$ связаны в $G-e$ этим же путем. Если же $e = e_i$ для некоторого $i \in \{1, 2, \dots, k\}$, то в графе $G-e$ существует $(u, v)$-маршрут, который обходит ребро $e$ по остальной части цикла: $e_1, \dots, e_{i-1}, e'_1, \dots, e'_l, e_{i+1}, \dots, e_k$. Следовательно, в любом случае $u$ и $v$ связаны в $G-e$. $\square$